package src.leetcode.hot.hard_0295;

import java.util.PriorityQueue;

public class MedianFinder {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.addNum(1);
        System.out.println(solution.findMedian());
        solution.addNum(2);
        System.out.println(solution.findMedian());
        solution.addNum(7);
        System.out.println(solution.findMedian());
        solution.addNum(4);
        System.out.println(solution.findMedian());
        solution.addNum(-1);
        System.out.println(solution.findMedian());
        solution.addNum(2);
        System.out.println(solution.findMedian());
//        PriorityQueue<Integer> leftpq = new PriorityQueue<>((a, b) -> b - a);
//        leftpq.add(1);
//        leftpq.add(31);
//        leftpq.add(-10);
//        leftpq.add(2);
//        leftpq.add(5);
//        while (!leftpq.isEmpty()) {
//            System.out.println(leftpq.peek());
//            System.out.println(leftpq.poll());
//        }
    }
}

class Solution {
    PriorityQueue<Integer> leftpq;
    PriorityQueue<Integer> rightpq;
    int mid;
    boolean flag;

    public Solution() {
        leftpq = new PriorityQueue<>((a, b) -> {
            return a > b ? -1 : 1;
        });
        leftpq.add(Integer.MIN_VALUE);
        rightpq = new PriorityQueue<>((a, b) -> a - b);
        rightpq.add(Integer.MAX_VALUE);
        mid = 0;
        flag = false;
    }

    public void addNum(int num) {
        if (flag) {
            if (num >= leftpq.peek() && num <= rightpq.peek()) {
                leftpq.add(Math.min(mid, num));
                rightpq.add(Math.max(mid, num));
            } else if (num < leftpq.peek()) {
                leftpq.add(num);
                rightpq.add(mid);
            } else {
                leftpq.add(mid);
                rightpq.add(num);
            }
            flag = false;
        } else {
            if (num >= leftpq.peek() && num <= rightpq.peek()) {
                mid = num;
            } else if (num < leftpq.peek()) {
                mid = leftpq.poll();
                leftpq.add(num);
            } else {
                mid = rightpq.poll();
                rightpq.add(num);
            }
            flag = true;
        }
    }

    public double findMedian() {
        if (flag) {
            return (double)mid;
        } else {
            return (leftpq.peek() + rightpq.peek()) / 2.0;
        }
    }
}